Distributed computing techniques can be used to speed up processing of computer applications by distributing workloads across numerous processing devices. Often, the workloads are organized into “jobs” that include individual “tasks” suitable for execution on a single device. Distributed computing techniques can allow jobs to be completed in relatively short periods of time by concurrently executing tasks of a job on different computing devices. However, in some cases, dependencies exist such that some tasks cannot be started until other tasks have finished. Because of these dependencies, not all tasks can be executed concurrently, which can slow down the processing of jobs in distributed computing systems. This problem can be compounded when a particular task runs for a long time, because other tasks with dependencies on the long-running task cannot start executing until the long-running task has completed.
One approach to mitigating the impact of dependencies in a distributed system is to duplicate long-running tasks. For example, a new copy of a long-running task may be instantiated on another computing device in the distributed system. Often, the copy of the long-running task will complete before the original copy of the long-running task, thus enabling other tasks with dependencies on the long-running task to begin executing sooner than would be possible by waiting for the long-running task to complete. However, in some cases, task duplication can have negative consequences, because task duplication generally requires using computing resources that would otherwise be available for other tasks that do not have such dependencies.